package Midium;

import java.util.Arrays;
//31.下一个排列
//没思路，直接看的答案
//1.我们需要将一个左边的「较小数」与一个右边的「较大数」交换，以能够让当前排列变大，从而得到下一个排列。
//2.同时我们要让这个「较小数」尽量靠右，而「较大数」尽可能小。当交换完成后，「较大数」右边的数需要按照升序重新排列。这样可以在保证新排列大于原来排列的情况下，使变大的幅度尽可能小。
//我只想到了第一点和第二点的较小数尽量靠右，没有想到较小数的尽可能小
public class Solution31 {
    public void nextPermutation(int[] nums) {
        int i;
        //寻找较小数
        for(i = nums.length-1;i>0;i--){
            if(nums[i]>nums[i-1]){
                break;
            }
        }
        if(i==0) {
            Arrays.sort(nums);
            return;
        }
        //得到较小数位置
        i--;
        //寻找较大数
        int j;
        for(j=nums.length-1;j>i;j--){
            if(nums[j]>nums[i])
                break;
        }
        //交换位置
        int temp = nums[j];
        nums[j]=nums[i];
        nums[i]=temp;
        //i现在是较大数的位置，将其后面的数进行排序（此时i后面必然是降序数组，所以直接对其进行翻转，而不是排序）
        for(i++,j=nums.length-1;i<j;i++,j--){
            temp = nums[j];
            nums[j]=nums[i];
            nums[i]=temp;
        }
    }

    public static void main(String[] args) {
        Solution31 s31 = new Solution31();
        s31.nextPermutation(new int[]{1,2,3});
    }
}
